#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 哈夫曼树的定义 */
typedef int TElemSet;
typedef struct BinaryTreeNode *HuffmanTree;
struct BinaryTreeNode {
    TElemSet weight; /* 权重 */
    char data; /* 字符 */
    HuffmanTree left; /* 左孩子指针 */
    HuffmanTree right; /* 右孩子指针 */
};
/* 哈夫曼树的定义结束 */

/* 树的集合的定义，即树结点的单链表 */
typedef HuffmanTree SetType;
typedef struct SetNode *Position; /* 指针即结点位置 */
struct SetNode {
    SetType data; /* 存储数据*/
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *TreeSet;
struct HeadNode {
    Position head; /* 单链表头指针 */
    int length; /* 表长 */
};

void InitTreeSet(TreeSet tree_set) {
    tree_set->head = NULL;
    tree_set->length = 0;
}

void Insert(TreeSet tree_set, SetType tree) {
    Position p;

    p = (Position)malloc(sizeof(struct SetNode));
    p->data = tree;
    p->next = tree_set->head;
    tree_set->head = p;
    tree_set->length++;
}

SetType ExtractMin(TreeSet tree_set) {
    TElemSet minw; /* 记录最小权重值 */
    Position pre_minp; /* 指向最小值结点的前一个结点 */
    Position p, tmp;
    SetType tree;

    if (tree_set->length == 0) {
        return NULL; /* 空集则返回空指针 */
    }
    tmp = (Position)malloc(sizeof(struct
                                  SetNode)); /* 方便起见加一个临时头结点 */
    tmp->next = tree_set->head;
    tree_set->head = tmp;
    pre_minp =
        tmp; /* 初始化最小值为第1个结点，pre_minp为空头结点 */
    p = tmp->next;
    minw = p->data->weight;
    while (p->next != NULL) {
        if (p->next->data->weight < minw) { /* 若下一个结点值更小 */
            minw = p->next->data->weight; /* 更新最小值 */
            pre_minp = p;
        }
        p = p->next;
    }
    p = pre_minp->next; /* p指向最小值结点 */
    pre_minp->next = p->next; /* 删除pre_minp后面的结点 */
    tree_set->length--;
    tree = p->data;
    free(p);
    tmp = tree_set->head; /* 删除临时空头结点 */
    tree_set->head = tmp->next;
    free(tmp);
    return tree;
}
/* 树的集合的定义结束 */

/* 权重集合的定义，即权重的数组 */
#define kMaxSize 10000
#define NIL -1
typedef TElemSet ElemSet;
typedef struct ListNode *List;
struct ListNode {
    ElemSet data[kMaxSize]; /* 存储数据的数组 */
    char c[kMaxSize]; /* 存储字符的数组 */
    int last; /* 线性表中最后一个元素在数组中的位置 */
};
void InitList(List list) {
    list->last = -1;
}

int Length(List list) {
    return (list->last + 1); /* 返回list的长度 */
}
/* 权重集合的定义结束 */

HuffmanTree CreateHuffmanTree(List w) {
    HuffmanTree tree;
    TreeSet tree_set;
    int n, i;

    tree_set = (TreeSet)malloc(sizeof(struct HeadNode));
    InitTreeSet(tree_set); /* 二叉树集合的初始化 */
    n = Length(w); /* n个权重 */
    for (i = 0; i < n; i++) { /* 初始化n个二叉树 */
        tree = (HuffmanTree)malloc(sizeof(struct BinaryTreeNode)); /* 创建叶结点 */
        tree->left = NULL;
        tree->right = NULL;
        tree->weight = w->data[i]; /* 从数据集w中取出一个权重 */
        tree->data = w->c[i]; /* 从数据集w中取出一个字符 */
        Insert(tree_set, tree);
    }
    for (i = 1; i < n; i++) { /* 合并二叉树，共n-1次 */
        tree = (HuffmanTree)malloc(sizeof(struct
                                          BinaryTreeNode)); /* 新建树根结点 */
        tree->left = ExtractMin(
                         tree_set); /* 取出根权重最小树作为左子树 */
        tree->right = ExtractMin(
                          tree_set); /* 取出根权重最小树作为右子树 */
        tree->weight = tree->left->weight +
                       tree->right->weight; /* 设置新树的根权重 */
        Insert(tree_set, tree); /* 将新树插入集合tree_set */
    }
    tree = ExtractMin(
               tree_set); /* 取出集合中唯一的二叉树，即哈夫曼树 */
    return tree;
}

/* 算法5-16：对二进制字符串解码 Decoding(tree, binary_code) */
void Decoding(HuffmanTree tree, char binary_code[]) {
    HuffmanTree p;
    int n, i;

    p = tree; /* 指向树根 */
    n = strlen(binary_code); /* 二进制字符串长度 */
    for (i = 0; i < n; i++) {
        if (binary_code[i] == '0') {
            p = p->left; /* 遇到0, 沿左分支下移 */
        } else { /* binary_code[i]=='1' */
            p = p->right;
        }
        if (p->left == NULL && p->right == NULL) { /* 到达叶结点 */
            printf("%c", p->data); /* 输出文字符 */
            p = tree; /* 返回树根，重新开始解码 */
        }
    }
}
/* 算法5-16 结束 */

int main(void) {
    int n, i;
    List w;
    HuffmanTree tree;
    char binary_code[kMaxSize];

    scanf("%d\n", &n);
    w = (List)malloc(sizeof(struct ListNode));
    InitList(w);
    for (i = 0; i < n; i++) {
        scanf("%c %d\n", &w->c[i], &w->data[i]);
        w->last++;
    }
    tree = CreateHuffmanTree(w);
    scanf("%s\n", binary_code);
    Decoding(tree, binary_code);

    return 0;
}